Technical Field
This application relates generally to data storage and more particularly to persistent, fault-tolerant data storage systems.
Brief Description of the Related Art
In a quorum-based data storage architecture, a data store is divided into multiple shards (also referred to as partitions) for parallel access. Replicas of each shard are stored in different nodes for improved persistency and fault tolerance, in the event of a node failure. The number of replicas per shard is typically configurable.
For read and write operations to a shard, a quorum of replicas is required. The quorum is the minimum number of replicas to successfully read or write data in order for a read or write operation to the shard to be considered successful. For example, assume that number of replicas per shard has been configured to be 5, and a quorum of 3 replicas is required for a successful operation. When a write operation returns a successful response, at least 3 of 5 replicas have the updated data. The other 2 replicas may have the data, but also may still be holding stale data or not have the data at all. Similarly, when a read operation returns a successful response, it means that at least 3 of 5 replicas had the same data, but the other 2 may not. If the other 2 replicas are alive, then eventually the data from the 3 replicas in the quorum that have the current data can be propagated over to other 2, enabling the replica set to achieve coherence.
When a shard is missing a quorum of replicas, for example due to a node failure or communication failure or other problem, then the entire shard is inaccessible because the quorum criteria cannot be met. Moreover, the most recently committed updates may be lost because those updates may be stored only in the write-successful replicas, which may be some or all of those that are missing.
To address this issue, missing replicas must be repaired. However, repairing missing replicas is challenging. For a high-performance data store, it is preferable that a repair occurs quickly, while maintaining data availability and persistency.
The teachings hereof address these technical challenges, among others, and provide a variety of benefits and improvements that will become apparent in view of this disclosure. The teachings hereof thus can provide improvements and benefits to the operation of distributed data storage technologies themselves, and in particular to replicated, quorum-based data storage, including distributed databases. The teachings hereof can be used to improve the operation of such systems, including in particular the data persistence and availability in such data storage systems.